import java.util.Random;

public class 快速排序 {

    private static int getIndex(int per, int aft, int[] ints) {
        while (per < aft) {
            while (ints[per] <= ints[aft] && per < aft) {// 从后往前扫描
                aft--;
            }
            ints[aft] = ints[per] + ints[aft] - (ints[per] = ints[aft]);// 交换
            while (ints[per] <= ints[aft] && per < aft) {// 从前往后扫描
                per++;
            }
            ints[aft] = ints[per] + ints[aft] - (ints[per] = ints[aft]);// 交换
        }
        return aft;
    }

    private static void sort(int per, int aft, int[] ints) {
        if(per >= aft){
            return ;
        }
        int index=getIndex(per, aft, ints);
        sort(per, index - 1, ints);
        sort(index + 1, aft, ints);
    }

    private static final int N = 100000;
    public static void main(String[] args) {
        int[] ints = new int[N];
        int len = ints.length;
        Random random = new Random();
        for (int i = 0; i < len; i++) {
            ints[i] = random.nextInt(N);
        }
        Long start = System.currentTimeMillis();
        sort(0, len - 1, ints);
        Long end = System.currentTimeMillis();
        StringBuilder sb = new StringBuilder("");
        for (int i : ints) {
            sb.append(i).append(", ");
        }
        System.out.println((end - start) + " ms\n[" + sb.delete(sb.length() - 2, sb.length()) + "]");
    }
}
